package ru.usu.gv.utils;

import ru.usu.gv.core.GraphCanvas;
import ru.usu.gv.core.GraphEngine;
import ru.usu.gv.graph.Graph;
import ru.usu.gv.graph.Vertex;
import ru.usu.gv.uicomponents.listener.IChangeListener;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 @author Sergey Pupyrev 
 08.05.2007
 */

public class GraphAlgorithmHelper
{
	private static int a[][];
	private static boolean initialized = false;

	static
	{
		GraphEngine.getInstance().getGraphListeners().addListener(new IChangeListener()
		{
			public void doChange(Object sender)
			{
				initialized = false;
			}
		});
	}

	public static synchronized void initializeFloydMatrix(int b[][])
	{
		if (!initialized)
		{
			Graph g = GraphCanvas.getInstance().getCurrentGraph().getGraph();
			initialized = true;
			Floyd(g);
		}

		for (int i = 0; i < a.length; i++)
			for (int j = 0; j < a[i].length; j++)
				b[i][j] = a[i][j];
	}

	private static void Floyd(Graph graph)
	{
		System.out.print("Floyd executing (n=" + graph.getSize() + ", m=" + graph.getEdgeSize() + ")...");
		long startTime = System.currentTimeMillis();

		int n = graph.getSize();
		a = new int[n][n];
		Floyd(graph, a);

		long endTime = System.currentTimeMillis();
		System.out.println("done (" + (endTime - startTime) / 1000.0 + " sec.)");
	}

	public static void Floyd(Graph graph, int[][] res)
	{
		int n = graph.getSize();
		assert (res.length == n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				res[i][j] = (i == j ? 0 : -1);

		for (int i = 0; i < n; i++)
		{
			Vertex v = graph.getVertex(i);
			for (int j = 0; j < v.getEdgesSize(); j++)
			{
				Vertex u = v.getEdge(j);
				int i1 = v.getIndex();
				int i2 = u.getIndex();

				res[i1][i2] = 1;
			}
		}

		for (int i = 0; i < n; i++)
		{
			int dist[] = new int[n];
			Arrays.fill(dist, -1);
			bfs(graph, i, dist);
			for (int j = 0; j < n; j++)
				res[i][j] = dist[j];

			if (n * n >= 1000000)
				if (i % 100 == 0)
					System.out.println("done " + i + "-th iteration");
		}
	}

	public static double[][] getDesiredDistances()
	{
		Graph graph = GraphCanvas.getInstance().getCurrentGraph().getGraph();
		return getDesiredDistances(graph);
	}

	public static double[][] getDesiredDistances(Graph graph)
	{
		int n = graph.getSize();
		int[][] dist = new int[n][n];
		initializeFloydMatrix(dist);
		double[][] res = new double[n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				res[i][j] = dist[i][j];// * StyleFacade.getEdgeLength();

		return res;
	}

	public static Map<Integer, Map<Integer, Double>> floyd(Map<Integer, Set<Integer>> edges)
	{
		Map<Integer, Map<Integer, Double>> result = new HashMap();
		for (Integer node : edges.keySet())
		{
			Map<Integer, Double> dist = new HashMap();
			bfs(edges, node, dist);
			dist.remove(node);
			result.put(node, dist);
		}

		return result;
	}

	private static void bfs(Map<Integer, Set<Integer>> edges, int node, Map<Integer, Double> dist)
	{
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(node);
		dist.put(node, 0.0);
		while (!queue.isEmpty())
		{
			node = queue.poll();
			for (Integer neig : edges.get(node))
			{
				if (!dist.containsKey(neig))
				{
					dist.put(neig, dist.get(node) + 1.0);
					queue.add(neig);
				}
			}
		}
	}

	private static void bfs(Graph graph, int now, int[] dist)
	{
		dist[now] = 0;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(now);
		while (!queue.isEmpty())
		{
			now = queue.poll();
			Vertex vnow = graph.getVertex(now);
			for (int i = 0; i < vnow.getEdgesSize(); i++)
			{
				int next = vnow.getEdge(i).getIndex();
				if (dist[next] == -1)
				{
					dist[next] = dist[now] + 1;
					queue.add(next);
				}
			}
		}
	}

	public static int[] bfs(Graph graph, int now)
	{
		int dist[] = new int[graph.getSize()];
		Arrays.fill(dist, -1);
		bfs(graph, now, dist);
		return dist;
	}

	public static int[] findClusterCenters(int a[][], int radius)
	{
		List<Integer> result = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++)
		{
			boolean ok = true;
			for (Integer j : result)
				if (a[i][j] >= 0 && a[i][j] <= radius)
				{
					ok = false;
					break;
				}

			if (ok)
				result.add(i);
		}

		int[] centers = new int[result.size()];
		for (int i = 0; i < result.size(); i++)
			centers[i] = result.get(i);
		return centers;
	}

	public static int getConnectedComponentsCount(Graph graph)
	{
		int result = 0;
		int n = graph.getSize();
		int dist[] = new int[n];
		Arrays.fill(dist, -1);
		for (int i = 0; i < n; i++)
			if (dist[i] == -1)
			{
				bfs(graph, i, dist);
				result++;
			}

		return result;
	}
}
